// poj3694
// 题意：n(<=100000)个点m(<=200000)边的无向图，有q(<=1000)个询问，问
//       加入一条边后图中桥的个数。
//
// 题解：先BCC，然后变成一个树。如果加的边在同一个点上，那么桥边不变。
//       这道题数据范围比较小，可以暴力将每次加入边两点到其lca上的桥边
//       标记为false。
//
//       其实可以有个优化，类似并查集的思想，将所有比如(x, y)到其lca上的
//       点的父亲都设成lca(x, y)，这样下次这些路径上的点就会被跳过，因为
//       不可能再有桥边。
//
// 统计：891ms
//
// run: $exec < input
#include <cstdio>
#include <algorithm>

int const maxn = 100010;
int const maxm = 200010;
int head[maxn], end_point[2 * maxm], next[2 * maxm];
int alloc;

int dfn[maxn], low[maxn], dep[maxn], parent[maxn];
bool bridge[maxn];
int tick;

int n, m, bridge_count;

void add_edge(int u, int v)
{
	end_point[alloc] = v; next[alloc] = head[u]; head[u] = alloc++;
	end_point[alloc] = u; next[alloc] = head[v]; head[v] = alloc++;
}

void init()
{
	alloc = 1; tick = 0; bridge_count = 0;
	for (int i = 0; i <= n; i++) head[i] = dfn[i] = bridge[i] = dep[i] = 0;
}

// tarjan find bridge
void dfs(int u, int par)
{
	dfn[u] = low[u] = ++tick;
	dep[u] = dep[parent[u]] + 1;
	for (int p = head[u]; p; p = next[p]) {
		int v = end_point[p];
		if (v == par) continue;
		if (!dfn[v]) {
			parent[v] = u;
			dfs(v, u);
			low[u] = std::min(low[u], low[v]);
			if (low[v] > dfn[u]) { bridge_count++; bridge[v] = true; }
		} else
			low[u] = std::min(low[u], dfn[v]);
	}
}

int lca(int u, int v)
{
	if (dep[u] < dep[v]) std::swap(u, v);
	for (; dep[u] > dep[v]; u = parent[u])
		if (bridge[u]) bridge[u] = false, bridge_count--;
	for (; u != v; u = parent[u], v = parent[v]) {
		if (bridge[u]) bridge[u] = false, bridge_count--;
		if (bridge[v]) bridge[v] = false, bridge_count--;
	}
	return bridge_count;
}

int main()
{
	for (int ti = 1; std::scanf("%d %d", &n, &m) && (n || m); ti++) {
		init();
		for (int i = 0, x, y; i < m; i++) {
			std::scanf("%d %d", &x, &y);
			add_edge(x, y);
		}
		dfs(1, 0);

		std::printf("Case %d:\n", ti);
		int q; std::scanf("%d", &q);
		for (int i = 0, x, y; i < q; i++) {
			std::scanf("%d %d", &x, &y);
			std::printf("%d\n", lca(x, y));
		}
		std::printf("\n");
	}
}

